239. Sliding Window Maximum.go

package leetcode

// 解法一 暴力解法 O(nk)
funcmaxSlidingWindow1(a []int, kint) []int {
res:=make([]int, 0, k)
n:=len(a)
ifn==0 {
return []int{}
 }
fori:=0; i<=n-k; i++ {
max:=a[i]
forj:=1; j<k; j++ {
ifmax<a[i+j] {
max=a[i+j]
 }
 }
res=append(res, max)
 }

returnres
}

// 解法二 双端队列 Deque
funcmaxSlidingWindow(nums []int, kint) []int {
iflen(nums) ==0||len(nums) <k {
returnmake([]int, 0)
 }
window:=make([]int, 0, k) // store the index of nums
result:=make([]int, 0, len(nums)-k+1)
fori, v:=rangenums { // if the left-most index is out of window, remove it
ifi>=k&&window[0] <=i-k {
window=window[1:]
 }
forlen(window) >0&&nums[window[len(window)-1]] <v { // maintain window
window=window[0 : len(window)-1]
 }
window=append(window, i) // store the index of nums
ifi>=k-1 {
result=append(result, nums[window[0]]) // the left-most is the index of max value in nums
 }
 }
returnresult
}